//
//  main.c
//  求解兑换钱的问题
//
//  Created by apple on 2016/12/19.
//  Copyright © 2016年 apple. All rights reserved.
//

#include <stdio.h>
#define MAX_SIZE 100

int main(){
    int money[MAX_SIZE +1];
    int base[]={1,3,4};
    int k=sizeof(base)/sizeof(int);
    int n,i,j;//n为要充换的钱数
    int m;
    printf("面额值：");
    for (i=0; i<k; i++) {
        printf("%6d",base[i]);
        }
    printf("\n输入要兑换的钱数：");
    scanf("%d",&n);
    money[0]=0;
    money[1]=1;
    for (i=2; i<=n; i++) {
        m=money[i-base[0]];
        for (j=1; j<k; j++) {
            if (i-base[j]>=0) {
                m=money[i-base[j]]<m?money[i-base[j]]:m;//三目运算符：对于b？x：y先判断b再判断，btrue计算x，否则计算y
            }
        }
                
        money[i]=m+1;
    }
    printf("最少兑换钞票张数：%d\n",money[n]);
    return 0;
    
}